<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
        1. 核心逻辑: 
            1.1 'abc' 'cc''abd' 比较每一个字符串的最后一个字符 再比较倒数第二个，以此类推 直到比较第一个
        1. 具体的细节：
            1.1 需要知道最长的字符串是多少 进而知道要总共比较多少趟
            1.2 'abc' 'ab' 如果像ab这样少了一个字符，就用 0 替代 ，0的ASCLL值是比'a'小的['a'.charCodeAt('0')是97 而0是48]
            【难点】 如果实现 缺失的部分用0去补足
            1.3 每一层里面使用计数排序 需要countArray 计数的数组，需要进行往前累加一位，需要倒序遍历原始数列，根据统计数列的值找到位置进行赋值
            每次排序完以后需要进行数组的赋值 给到下一次的拷贝使用【必须用到深拷贝】
        2. 时间复杂度 O( n(m + k)) m+k表示原始数组和统计数组的遍历，n表示最大的字符数量
        3. 空间复杂度  O(m+n)m是统计数组 n是结果数组的值
        
        */
        function radixSort(nums) {
            let ASCII_RANGE = 128
            // 找到数组里面的长度最大的元素 作为比较的次数
            let max = nums[0].length;
            for (let item of nums) {
                if (item.length > max) {
                    max = item.length
                }
            }
            // 排序结果数组
            let sortedArray = new Array(nums.length)
            // 从个位开始比较 一直比较到最高位
            for (let k = max - 1; k >= 0; k--) {
                // 里面使用计数排序 分成3步
                // 1. 创建辅助排序的统计数组 并把待排序的字符对号入座
                // 这个数组必须每个位数比较都要重新创建一次
                let countArray = new Array(ASCII_RANGE).fill(0)
                for (let i = 0; i < nums.length; i++) {
                    // nums[i] => 数组里面第i个字符 => 获取该字符对应k位的字符的ACSLL值
                    let index = getCharIndex(nums[i], k)
                    countArray[index]++
                }

                // 2. 统计数组做变形 后面的元素等于前面的元素之和 => 后一项的值等于(当前后一项的值 + 前一项的值)
                for (let i = 1; i < countArray.length; i++) {
                    countArray[i] = countArray[i] + countArray[i - 1]
                }
                // 3. 倒序遍历原始数列，从统计数组找到正确的位置 输出到结果数组
                /* 
                    难以理解的点：
                    1. 为什么一定是倒序遍历呢？
                */
                for (let i = nums.length - 1; i >= 0; i--) {
                    // 最难以理解的点：
                    // getCharIndex(nums[i], k)的值得到的index是对应的ASCLL码的值
                    // ASCLL码的值在countArray里面对应的值 - 1 就是对应应该放到的位置
                    // 比如 'aaa' 'aab' 'aac' 'aad' 'aae' -> countArray[……, 1, 1, 1, 1, 1] -> [……, 1, 2, 3, 4, 5] 那么'aae'这个值得到的是5，我们应该放在索引为4的位置
                    let index = getCharIndex(nums[i], k)
                    let position = countArray[index] - 1
                    sortedArray[position] = nums[i]
                    countArray[index]--
                }
                // 这次排序的结果 给下一次排序使用 -> 下一次指代 第二位的字符
                nums = JSON.parse(JSON.stringify(sortedArray))
                // nums = sortedArray
            }
            return nums
        }

        // 获取字符串第k位字符的ACSLL数
        function getCharIndex(str, k) {
            debugger
            // 如果字符串的长度小于k 直接返回0 相当于给不存在的位置补0
            if (str.length < (k + 1)) {
                return 0
            }
            return str.charCodeAt(k)
        }
        let arr2 = ['qd', 'abc', 'qwe', 'hhh', 'a', 'cws', 'ope']
        console.log(radixSort(arr2));
        // let arr0 = ['282', '382', '484', '181', '141']
        // let arr1 = ['18914021920', '13223132981', '13566632981', '13660891039', '13361323035']
        // let arr3 = ['banana', 'apple', 'orange', 'ape', 'he']
        // let arr4 = ['bda', 'cfd', 'yui', 'abc', 'rrr', 'uue', 'qwe']
        // console.log(radixSort(arr1));
        // console.log(radixSort(arr0));
        // console.log(radixSort(arr3));
        // console.log(radixSort(arr3));
        // console.log(radixSort([5, 2, 3, 1]));
    </script>
</body>

</html>